// https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock/description

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        int min = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); ++i)
        {
            if (prices[i] < min) min = prices[i];
            int tmp = prices[i] - min;
            if (tmp > result) result = tmp;
        }
        return result;
    }
};